// https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

/*
给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

*/
#include <string>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>

using namespace std;

class Solution {
public:
	// 最笨的方法，已经通过
	/*
	执行用时：
1444 ms
, 在所有 C++ 提交中击败了
5.02%
的用户

内存消耗：
443.5 MB
, 在所有 C++ 提交中击败了
5.05%
的用户
	*/
    vector<int> findSubstring(string s, vector<string>& words) {
		int len = words.size();
		int sLen = s.size();
		int wLen = words[0].size();
		int wordsLen = len * wLen;
		vector<int> res;
		multiset<string> ms;
		for(auto w : words){
			ms.insert(w);
		}
		cout << sLen - wordsLen << endl;
		for(int i = 0; i < sLen - wordsLen + 1; i++){
			multiset<string> tmpSet = ms;
			for(int j = i; j < i + wordsLen; j = j + wLen){
				string tmp = s.substr(j, wLen);
				auto it = tmpSet.find(tmp);
				if(it == tmpSet.end()){
					break;
				}
				tmpSet.erase(it);
			}
			if(tmpSet.empty()){
				res.push_back(i);
			}else{
				
			}
		}
		return res;
    }
	
	// 优化方法 使用map速度可以提升8倍，内存减少20倍
	/*
	执行用时：
164 ms
, 在所有 C++ 提交中击败了
55.71%
的用户
内存消耗：
23.9 MB
, 在所有 C++ 提交中击败了
54.80%
的用户
	*/
	
	vector<int> findSubstring1(string s, vector<string>& words) {
		int len = words.size();
		int sLen = s.size();
		int wLen = words[0].size();
		int wordsLen = len * wLen;
		vector<int> res;
		unordered_map<string,int> um;
		for(auto w : words){
			um[w]++;
		}
		
		for(int i = 0; i < sLen - wordsLen + 1; i++){
			unordered_map<string,int> tmpMap;
			int j = 0;
			for(j = 0; j < len; j++){
				string tmp = s.substr(i + j * wLen, wLen);
				if(!um.count(tmp)) break;
				if(++tmpMap[tmp] > um[tmp]) break;
			}
			if(j == len){
				res.push_back(i);
			}
		}
		return res;
    }
};

int main(){
	string s = "wordgoodgoodgoodbestword";
	vector<string> words = {"word","good","best","good"};
	Solution so;
	vector<int> res = so.findSubstring1(s, words);
	cout << 123 <<endl;
	for(auto i : res){
		cout << i << ",";
	}
	cout << endl;
	return 0;
}